﻿#include <iostream>
#include <vector>
using namespace std;
double gp_2d(int n) {
	double res = 1.;
	if (n == 0) return 1;
	else if (n < 0) res = gp_2d(n + 1) / 2.;
	else res = gp_2d(n - 1) * 2.;
	return res;
}
int gp_2i(int n) {
	if (n == 0) return 1;
	else if (n < 0) return gp_2d(n);
	else return 2 * gp_2i(n-1);
}
long factorial(int n) {
	if (n < 0) return -1; 
	return (n == 0) ? 1 : n * factorial(n - 1);
}
long unsigned fibonacci_dg(int n) {
	//return (n < 0) ? -1 : (n == 0) ? 0 : (n == 1 || n == 2) ? 1 : fibonacci_dg(n - 1) + fibonacci_dg(n - 2);(疑似炫技哈，美死了)
	if (n < 0) return -1;
	else if (n == 0 ) return 0;
	else if (n == 1|| n == 2) return 1;
	else return fibonacci_dg(n - 1) + fibonacci_dg(n - 2);
}
long fibonacci_dt(int n) {
	static vector<long> fib_vec = { 0, 1 };  // 静态 vector，初始化为 {0, 1}

	if (n < 0) return -1;
	if (n < fib_vec.size()) {  // 如果已计算，直接返回
		return fib_vec[n];
	}

	// 扩展 vector 并计算缺失的项
	while (fib_vec.size() <= n) {
		int size = fib_vec.size();
		fib_vec.push_back(fib_vec[size - 1] + fib_vec[size - 2]);
	}

	return fib_vec[n];
}
int main(){
	/*
	int a = gp_2i(3) ;
	double b = gp_2d(-4) ;
	cout << "2的3次方是: " << a << endl;
	cout << "2的-4次方是: " << b << endl;
	*/
	/*for (size_t i = 1; i <= 10; i++){
		cout<< i << "的阶乘是: " << factorial(i) << endl;
	}*/
	for (size_t i = 1; i <= 50; i++) {
		cout << "第" << i << "项斐波那契数列的值是: " << fibonacci_dt(i) << endl;
	}
	/*for (size_t i = 1; i <= 50; i++) {
		cout << "第"  << i << "项斐波那契数列的值是: " << fibonacci_dg(i) << endl;
	}*/
	return 0;
}